#include "../tools.h"

class Solution {
public:
    int searchLeft(vector<int>& nums, int target){
        int left = 0, right = nums.size();
        while(left < right){    // 终止条件是 left == right
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                right = mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }
        }
        // ！需要处理越界，正确理解左边界查找 & 右边界查找的意义
        return (left >= nums.size() || nums[left] != target) ? -1: left;
    }
    int searchRight(vector<int>& nums, int target){
        int left = 0, right = nums.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                left = mid + 1;
            }else if(target < nums[mid]){
                right = mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }
        }
        return (left  - 1 < 0 || nums[left  - 1] != target) ? -1: left  - 1;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};
        if(nums.size() == 1){
            if(nums[0] == target) return {0, 0};
            else return {-1, -1};
        }

        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        return {left, right};
    }
};